﻿namespace AdvancedTraining.Lesson40;

/// <summary>
/// 让A有序的问题
/// </summary>
/// <remarks>
/// 给定两个数组A和B，长度都是N
/// A[i]不可以在A中和其他数交换，只可以选择和B[i]交换(0<=i<n)
/// 你的目的是让A有序，返回你能不能做到
///
/// 算法思路：
/// 使用递归回溯的方法，在每个位置i有两种选择：
/// 1. 不交换：使用A[i]作为当前位置的值
/// 2. 交换：使用B[i]作为当前位置的值
///
/// 通过递归尝试所有可能的交换组合，检查是否能得到有序的A数组
///
/// 时间复杂度：O(2^N)，最坏情况下需要尝试所有交换组合
/// 空间复杂度：O(N)，递归调用栈的深度
/// </remarks>
public class LetASorted
{
    /// <summary>
    /// 方法一：让A按升序排列
    /// </summary>
    /// <param name="a">数组A</param>
    /// <param name="b">数组B</param>
    /// <returns>是否能让A按升序排列</returns>
    public static bool LetASortedCode1(int[] a, int[] b)
    {
        return Process(a, b, 0, int.MinValue);
    }

    /// <summary>
    /// 方法二：让A按降序排列
    /// </summary>
    /// <param name="a">数组A</param>
    /// <param name="b">数组B</param>
    /// <returns>是否能让A按降序排列</returns>
    public static bool LetASortedCode2(int[] a, int[] b)
    {
        // 修复：要让A降序排列，初始值应该是int.MaxValue
        return Process2(a, b, 0, int.MaxValue);
    }

    // 当前推进到了i位置，对于A和B都是i位置
    // A[i]前一个数字，lastA
    // 能否通过题意中的操作，A[i] B[i] 让A整体有序
    private static bool Process(int[] a, int[] b, int i, int lastA)
    {
        if (i == a.Length) return true;
        // 第一种选择 : A[i]不和B[i]交换
        if (a[i] >= lastA && Process(a, b, i + 1, a[i])) return true;
        // 第一种选择 : A[i]和B[i]交换
        if (b[i] >= lastA && Process(a, b, i + 1, b[i])) return true;
        return false;
    }

    private static bool Process2(int[] a, int[] b, int i, int lastA)
    {
        if (i == a.Length) return true;
        // 第一种选择 : A[i]不和B[i]交换
        if (a[i] <= lastA && Process2(a, b, i + 1, a[i])) return true;
        // 第一种选择 : A[i]和B[i]交换
        if (b[i] <= lastA && Process2(a, b, i + 1, b[i])) return true;
        return false;
    }

    // A B 操作 : A[i] 与 B[i] 交换！
    // 目的 : 让A和B都有序，能不能做到
    //	private static boolean Process3(int[] A, int[] B, int i, int lastA, int lastB) {
    //
    //	}

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== LetASorted 测试 ===");

        // 测试用例1：原示例
        var a1 = new int[] { 3, 2, 2 };
        var b1 = new int[] { 1, 2, 3 };
        Console.WriteLine($"测试1 - 升序排列: A=[{string.Join(",", a1)}], B=[{string.Join(",", b1)}]");
        Console.WriteLine($"结果: {LetASortedCode1(a1, b1)} (期望: True)");
        Console.WriteLine($"测试1 - 降序排列: A=[{string.Join(",", a1)}], B=[{string.Join(",", b1)}]");
        Console.WriteLine($"结果: {LetASortedCode2(a1, b1)} (期望: True)");
        Console.WriteLine();

        // 测试用例2：已经有序的情况
        var a2 = new int[] { 1, 2, 3 };
        var b2 = new int[] { 4, 5, 6 };
        Console.WriteLine($"测试2 - 升序排列(已有序): A=[{string.Join(",", a2)}], B=[{string.Join(",", b2)}]");
        Console.WriteLine($"结果: {LetASortedCode1(a2, b2)} (期望: True)");
        Console.WriteLine($"测试2 - 降序排列: A=[{string.Join(",", a2)}], B=[{string.Join(",", b2)}]");
        Console.WriteLine($"结果: {LetASortedCode2(a2, b2)} (期望: False)");
        Console.WriteLine();

        // 测试用例3：不可能有序的情况
        var a3 = new int[] { 5, 1, 2 };
        var b3 = new int[] { 3, 4, 6 };
        Console.WriteLine($"测试3 - 升序排列: A=[{string.Join(",", a3)}], B=[{string.Join(",", b3)}]");
        Console.WriteLine($"结果: {LetASortedCode1(a3, b3)} (期望: True)");
        Console.WriteLine($"测试3 - 降序排列: A=[{string.Join(",", a3)}], B=[{string.Join(",", b3)}]");
        Console.WriteLine($"结果: {LetASortedCode2(a3, b3)} (期望: True)");
        Console.WriteLine();

        // 测试用例4：单个元素
        var a4 = new int[] { 5 };
        var b4 = new int[] { 3 };
        Console.WriteLine($"测试4 - 升序排列(单元素): A=[{string.Join(",", a4)}], B=[{string.Join(",", b4)}]");
        Console.WriteLine($"结果: {LetASortedCode1(a4, b4)} (期望: True)");
        Console.WriteLine($"测试4 - 降序排列(单元素): A=[{string.Join(",", a4)}], B=[{string.Join(",", b4)}]");
        Console.WriteLine($"结果: {LetASortedCode2(a4, b4)} (期望: True)");
        Console.WriteLine();

        // 测试用例5：完全不可能的情况
        var a5 = new int[] { 2, 1 };
        var b5 = new int[] { 1, 2 };
        Console.WriteLine($"测试5 - 升序排列(复杂): A=[{string.Join(",", a5)}], B=[{string.Join(",", b5)}]");
        Console.WriteLine($"结果: {LetASortedCode1(a5, b5)} (期望: True)");
        Console.WriteLine($"测试5 - 降序排列(复杂): A=[{string.Join(",", a5)}], B=[{string.Join(",", b5)}]");
        Console.WriteLine($"结果: {LetASortedCode2(a5, b5)} (期望: True)");
        Console.WriteLine();

        Console.WriteLine("=== 测试完成 ===");
    }
}